package common.tree;

import java.util.*;
import java.util.function.Function;
import java.util.function.Predicate;

/**
 * 树的实现类
 * @author ：Sei
 * @param <K> 树节点的键
 * @param <N> 树节点泛型
 */
public class Tree<K, N extends ITreeNode<K, N>> extends AbstractTree<K, N> implements ITree<K, N> {

    private List<N> nodes;

    private Map<K, List<N>> nodeMap;

    private Map<K, N> selfMap;

    private N root;

    private Tree(){}
    private Tree(List<N> nodes){
        this.nodes = nodes;
        init(nodes);
    }

    public static <K, N extends ITreeNode<K,N>> Tree<K, N> create(List<N> lst){
        return new Tree<>(lst);
    }

    public Tree<K, N> add(N node){
        if(null == node || this.selfMap.containsKey(node.getKey()) || !this.selfMap.containsKey(node.getParentKey())){
            return this;
        }
        this.nodes.add(node);
        init(nodes);
        return this;
    }

    //region 实例方法
    @Override
    public List<N> findUp(N node, Predicate<N> searcher) {
        return null;
    }

    @Override
    public N findUpFirst(N node, Predicate<N> searcher) {
        return null;
    }

    @Override
    public List<N> findDown(N node, Predicate<N> searcher) {
        return bfs(node, searcher);
    }

    @Override
    public N findDownFirst(N node, Predicate<N> searcher) {
        Queue<N> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            N currentNode = queue.poll();
            assert currentNode != null;
            for(N n : currentNode.getChilden()){
                if(searcher.test(n)){
                    return n;
                }
                queue.add(n);
            }
        }
        return null;
    }

    @Override
    public List<N> getParentsNode(N node) {
        return null;
    }

    @Override
    public List<N> getSubNode(N node) {
        return null;
    }

    @Override
    public List<N> getSubLeaf(N node) {
        return null;
    }

    @Override
    public N getParent(N node) {
        return null;
    }

    @Override
    public List<N> getChildren(N node) {
        return null;
    }

    @Override
    public Map<K, List<N>> mapByNodes() {
        return this.nodeMap;
    }

    @Override
    public Map<K, N> mapByNodesSelf() {
        return this.selfMap;
    }
    //endregion

    private boolean isLeaf(N node) {
        return false;
    }

    private void init(List<N> nodes){
        this.nodeMap = mapByNodes(nodes);
        this.selfMap = mapByNodesSelf(nodes);
        this.root = findRoot(nodes);
    }

    private N findRoot(List<N> nodes) {
        N cur;
        if(null == nodes || nodes.size() == 0){
            return null;
        }
        cur = nodes.get(0);
        while(null !=cur.getParentKey() && this.selfMap.get(cur.getParentKey())!=null){
            this.selfMap.get(cur.getParentKey());
        }
        return cur;
    }
}
